//package a2025_02_19;
//
//import javafx.util.Pair;
//  662 二叉树最大宽度
//  662 二叉树最大宽度
//  662 二叉树最大宽度
//  662 二叉树最大宽度
//  队列+宽搜
//  用数组，将节点和下标加入
//import javax.swing.tree.TreeNode;
//import java.util.ArrayList;
//
///**
// * Definition for a binary tree node.
// * public class TreeNode {
// *     int val;
// *     TreeNode left;
// *     TreeNode right;
// *     TreeNode() {}
// *     TreeNode(int val) { this.val = val; }
// *     TreeNode(int val, TreeNode left, TreeNode right) {
// *         this.val = val;
// *         this.left = left;
// *         this.right = right;
// *     }
// * }
// */
//class Solution {
//    public int widthOfBinaryTree(TreeNode root) {
//        List<Pair<TreeNode,Integer>> list=new ArrayList<>();
//        list.add(new Pair<>(root,1));
//        int ret=0;
//
//        while(!list.isEmpty()){
//            Pair<TreeNode,Integer> t1=list.get(0);
//            Pair<TreeNode,Integer> t2=list.get(list.size()-1);
//            获取链表收尾的节点的值，相当于获取每一层的最左和最右节点
//            ret=Math.max(ret,t2.getValue()-t1.getValue()+1);
//
//            List<Pair<TreeNode,Integer>> list2=new ArrayList<>();
//            for(Pair<TreeNode,Integer> temp:list){//将节点的非空左右节点加入链表
//                TreeNode node=temp.getKey();
//                int value=temp.getValue();
//                if(node.left!=null){
//                    list2.add(new Pair<>(node.left,value*2));
//                }
//                if(node.right!=null){
//                    list2.add(new Pair<>(node.right,value*2+1));
//                }
//            }
//            list=list2;
//        }
//        return ret;
//    }
//}